/*
 * flow.h
 *
 *  Created on: Jun 20, 2010
 *      Author: vincent
 */

#ifndef FLOW_H
#define FLOW_H

#include "opcode.h"
#include "debug.h"
#include "symbol.h"
#include <vector>
#include <deque>
#include <set>
#include <map>
#include <cassert>

class CFG;
class DomNode;
class DomTree;
class RegAlloc;

class BasicBlock{
private:
    // the first opcode's pc, used to debug
    int firstOp;

    /// the depth-first number, in reverse postorder
    int dfsNo;

    std::vector<Opcode*> ops;
    std::set<BasicBlock*>    preds;
    std::set<BasicBlock*>    succs;
public:
    BasicBlock(int i):firstOp(i),dfsNo(-1){};

    int     getId() const{return firstOp;};
    void    setDfsNo(int n){dfsNo = n;};
    int     getDfsNo()  const{return dfsNo;};

    void    insertOp(Opcode *o){ops.push_back(o);};

    /// insert a predecessor
    void    insertPred(BasicBlock* bb){preds.insert(bb);};

    /// insert a successor
    void    insertSucc(BasicBlock* bb){succs.insert(bb);};

    /// opcode iterator
    typedef std::vector<Opcode*>::iterator   iterator;

    /// opcode reverse iterator
    typedef std::vector<Opcode*>::reverse_iterator reverse_iterator;

    /// predecessor iterator
    typedef std::set<BasicBlock*>::iterator  pred_iterator;

    /// successor   iterator
    typedef std::set<BasicBlock*>::iterator  succ_iterator;

    iterator   begin(){return ops.begin();};
    iterator   end(){return ops.end();};

    reverse_iterator rbegin()
    {
        return ops.rbegin();
    }

    reverse_iterator rend()
    {
        return ops.rend();
    }

    pred_iterator   getPredBegin(){return preds.begin();};
    pred_iterator   getPredEnd(){return preds.end();};

    succ_iterator   getSuccBegin(){return succs.begin();};
    succ_iterator   getSuccEnd(){return succs.end();};

    const Opcode*   getLastOp(){return ops.back();}

};

class CFG{
private:
    /// START block
    BasicBlock  *startBlock;

    /// END block
    BasicBlock  *endBlock;

    /// all basic blocks excluding START and END
    std::vector<BasicBlock*>    blocks;

    /// the basic blocks in dfs number order(reverse postorder)
    std::deque<BasicBlock*>    blocksDfsOrder;

    /// the corresponding domTree
    DomTree *domTree;

    /// the symbol of this CFG's function
    FunctionSymbol  *funcSym;

    void    makeBlocks();
    void    setDfsNumber();
public:
    CFG(FunctionSymbol *sym);
    RegAlloc *regalloc;

    void    setup();
    BasicBlock*     getBlockByDfsno(int i);
    int     getDfsBlockSize(){return blocksDfsOrder.size();};
    const   BasicBlock* getStartBlock(){return startBlock;};
    const   BasicBlock* getEndBlock(){return endBlock;};
    void    printBlocks(GraphPrinter &gp);
    FunctionSymbol*    getFunctionSymbol() const{return funcSym;};
    DomTree*    getDomTree()  const{return domTree;};

    typedef std::vector<BasicBlock*>::iterator  iterator;
    iterator    begin(){return blocks.begin();};
    iterator    end(){return blocks.end();};

    /// iterator by dfs traversal of the CFG
    typedef std::deque<BasicBlock*>::iterator   dfs_iterator;
    typedef std::deque<BasicBlock*>::reverse_iterator   dfs_reverse_iterator;
    dfs_iterator    dfsBegin(){return blocksDfsOrder.begin();};
    dfs_iterator    dfsEnd(){return blocksDfsOrder.end();};
    dfs_reverse_iterator    dfsRbegin(){return blocksDfsOrder.rbegin();};
    dfs_reverse_iterator    dfsRend(){return blocksDfsOrder.rend();};
};

/// base class for analysis info node attached to each basicblock
class AnalysisNode{
protected:
    /// the corresponding BasicBlock
    BasicBlock  *bb;
public:
    AnalysisNode(BasicBlock *b):bb(b){
        assert(bb && "AnalysisNode requires a valid bb");
    };

    virtual ~AnalysisNode()
    {
        delete bb;
    };

    BasicBlock *getBB() const{return bb;};
};

// TODO: put these analysis templates to more suitable header file
template <typename T>
class AnalysisTraits{
public:
    typedef T   type;
    typedef std::map<BasicBlock*,T*>    link;
};

template <typename T>
class Analysis{
public:
    typedef typename AnalysisTraits<T>::type     analysis_type;
    typedef typename AnalysisTraits<T>::link     analysis_link_type;
    typedef typename AnalysisTraits<T>::link::iterator     analysis_iterator;
protected:
    CFG     *cfg;

    /// source level debug purpose
    LogPrinter  log;

    /// the map from bb to destinate analysis object
    analysis_link_type   nodes;

    Analysis(CFG *c){
        assert(c && "Analysis an empty CFG");
        cfg = c;
    }

    /// create the node associating with the basicblock
    virtual T*  createNode(BasicBlock* bb) = 0;

    T*   getOrCreateNode(BasicBlock* bb){
        analysis_iterator it = nodes.find(bb);

        if(it != nodes.end()){
            return it->second;
        }else{
            T* n = createNode(bb);
            nodes[bb] = n;
            return n;
        }
    }

    T*  getOrCreateNode(int blockDfsNo){
        BasicBlock *bb = cfg->getBlockByDfsno(blockDfsNo);
        assert(bb && "the cfg can't get the basicblock by this no.");

        return  getOrCreateNode(bb);
    }

};

class DomNode : public AnalysisNode{
private:
    /// the immediate dominator
    DomNode *idom;

    // nodes whose idom is this
    std::vector<DomNode*>    domee;
public:
    DomNode(BasicBlock *b):AnalysisNode(b),idom(0){};
    void    setIdom(DomNode *n){idom = n;};
    DomNode*    getIdom(){return idom;};
    void    addDomee(DomNode *n){domee.push_back(n);};

    typedef std::vector<DomNode*>::iterator     domee_iterator;
    domee_iterator  begin(){return domee.begin();};
    domee_iterator  end(){return domee.end();};
};


class DomTree : public Analysis<DomNode>{
private:
    typedef std::map<BasicBlock*,std::set<int> >    bb2df_type;

    /// the dominance frontiers for each block in domtree
    bb2df_type    domFrontiers;

    std::set<int>   allDomFrontiers;

    /// "two fingers" algorithm, compare postorder number
    int     intersect(int dno1,int dno2);
public:
    DomTree(CFG *c);
    void    buildDomTree();
    void    buildDomFrontier();

    virtual DomNode*    createNode(BasicBlock *bb);
    void    printBlocks(GraphPrinter &gp);

    typedef std::set<int>    df_set_type;
};

#endif // FLOW_H
